import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: xwl
 * Date: 2023-05-22
 * Time: 23:26
 */

// 节点类
class TreeNode5 {
    int val;
    TreeNode5 left;
    TreeNode5 right;
    TreeNode5() {}
    TreeNode5(int val) { this.val = val; }
    TreeNode5(int val, TreeNode5 left, TreeNode5 right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Test5 {
    public void postorderTraversal(TreeNode5 root) {
        // 讨论树为空的情况
        if (root == null) {
            return;
        }
        // 创建一个节点用来存当前节点
        TreeNode5 cur = root;
        //
        TreeNode5 prev = null;
        // 创建一个栈来存放节点
        Deque<TreeNode5> stack = new ArrayDeque<>();
        // 实现
        while (cur != null || !stack.isEmpty()) {
            // 判断
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 定义一个top来表示当前的元素
            TreeNode5 top = stack.peek();
            if (top.right == null || top.right == prev) {
                System.out.println(top.val);
                stack.pop();
                prev = top;
            }else {
                cur = top.right;
            }
        }
    }
}
